package acwing._1_1AlgorithmBasic;

/**
 * @Project : ProgrammingExercises
 * @Package : ACWing.AlgorithmTemplate
 * @File : _1_1Sort.java
 * @Author : WangRuoyu
 * @Date 2023/3/9 16:08
 */

public class _1_1Sort {
    // 快速排序
    static void quickSort(int[] q, int l, int r) {
        if (l >= r) {
            return;
        }
        int x = q[l];
        int i = l - 1;
        int j = r + 1;

        while (i < j) {
            while (q[++i] < x) ;
            while (q[--j] > x) ;
            if (i < j) {
                int tmp = q[i];
                q[i] = q[j];
                q[j] = tmp;
            }
        }

        quickSort(q, l, j);
        quickSort(q, j + 1, r);
    }

    //快速选择算法，时间复杂度O(n)
    static int quickChoose(int q[], int l, int r, int k) {
        if (l >= r) {
            return q[l];
        }
        int x = q[l];
        int i = l - 1;
        int j = r + 1;
        while (i < j) {
            while (q[++i] < x) ;
            while (q[--j] > x) ;
            if (i < j) {
                int tmp = q[i];
                q[i] = q[j];
                q[j] = tmp;
            }
        }
        int tmp = j - l + 1;
        if (k <= tmp) {
            return quickChoose(q, l, j, k);
        } else {
            return quickChoose(q, l + 1, r, k - tmp);
        }
    }

    // 快速选择2：一半快排
    static void quickChooseMy(int q[], int l, int r, int k) {
        if (l >= r) {
            return;
        }
        int x = q[l];
        int i = l - 1;
        int j = r + 1;
        while (i < j) {
            while (q[++i] < x) ;
            while (q[--j] > x) ;
            if (i < j) {
                int tmp = q[i];
                q[i] = q[j];
                q[j] = tmp;
            }
        }
        if (k <= j + 1) {
            quickChooseMy(q, l, j, k);
        } else {
            quickChooseMy(q, l + 1, r, k);
        }
    }

    // 归并排序（需要一个静态临时数组tmp）
    static int[] tmp = new int[1000010];

    static void mergeSort(int[] q, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        mergeSort(q, l, mid);
        mergeSort(q, mid + 1, r);

        int k = 0;
        int i = l;
        int j = mid + 1;

        while (i <= mid && j <= r) {
            if (q[i] <= q[j]) {
                tmp[k++] = q[i++];
            } else {
                tmp[k++] = q[j++];
            }
        }
        while (i <= mid) {
            tmp[k++] = q[i++];
        }
        while (j <= r) {
            tmp[k++] = q[j++];
        }

        for (int m = 0; m < k; ++m) {
            q[l + m] = tmp[m];
        }
    }

    static int[] tmp2 = new int[1000010];

    static long mergeSort_inversionPair(int[] q, int l, int r) {
        if (l >= r) {
            return 0;
        }

        int mid = (l + r) / 2;
        int i = l;
        int j = mid + 1;

        long res = mergeSort_inversionPair(q, l, mid) + mergeSort_inversionPair(q, mid + 1, r);

        int k = 0;
        while (i <= mid && j <= r) {
            if (q[i] <= q[j]) {
                tmp2[k++] = q[i++];
            } else {
                tmp2[k++] = q[j++];
                res += (mid - i + 1);
            }
        }

        while (i <= mid) {
            tmp2[k++] = q[i++];
        }
        while (j <= r) {
            tmp2[k++] = q[j++];
        }

        for (int m = 0; m < k; ++m) {
            q[l + m] = tmp2[m];
        }
        return res;
    }
}


